package LeetCode.month01.day20;

import java.util.Arrays;

public class No3363 {
    public static void main(String[] args) {
        System.out.println(maxCollectedFruits(new int[][]{{1,2,3,4},{5,6,8,7},{9,10,11,12},{13,14,15,16}}));
    }
    public static int maxCollectedFruits(int[][] fruits) {
        int n = fruits.length;
        int[][] dp = new int[n][n];
        dp[n - 1][0] = fruits[n - 1][0];
        dp[0][n - 1] = fruits[0][n - 1];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fruits[i][i];
            fruits[i][i] = 0;
        }
        for (int j = 1; j < n - 1; j++) {
            for (int i = n - 1; i > j && i >= n - j - 1; i--) {
                if (i < n - 1) {//不是最后一行
                    if (j == n - i - 1) {//只能由左下角而来
                        dp[i][j] = dp[i + 1][j - 1] + fruits[i][j];
                    } else if (j == n - i) {//由左边或左下来
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j - 1]) + fruits[i][j];
                    } else {
                        dp[i][j] = Math.max(Math.max(dp[i][j - 1], dp[i + 1][j - 1]), dp[i - 1][j - 1]) + fruits[i][j];
                    }
                } else {
                    if (j == 1) {
                        dp[i][j] = dp[i][j - 1] + fruits[i][j];
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - 1]) + fruits[i][j];
                    }
                }
            }
        }
        for (int i = 1; i < n - 1; i++) {
            for (int j = n - 1; j > i && j >= n - i - 1; j--) {
                if (j < n - 1) {//不是最后一列
                    if (j == n - i - 1) {//只能由右上角而来
                        dp[i][j] = dp[i -1][j+1] + fruits[i][j];
                    } else if (j == n - i) {//由上边或右上来
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j + 1]) + fruits[i][j];
                    } else {
                        dp[i][j] = Math.max(Math.max(dp[i-1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]) + fruits[i][j];
                    }
                } else {
                    if (i == 1) {
                        dp[i][j] = dp[i-1][j] + fruits[i][j];
                    } else {
                        dp[i][j] = Math.max(dp[i-1][j - 1], dp[i - 1][j]) + fruits[i][j];
                    }
                }
            }
        }
        return sum+dp[n-1][n-2]+dp[n-2][n-1];
    }
}
